1. Technical Field
The present invention relates generally to circuit design, and more particularly, to a method, system and program product for merging cloned and original circuit shapes.
2. Related Art
Hierarchical technology migration is an integral part of integrated circuit (IC) design methodologies and design optimization. One challenge with migration is addressing multiple orientations of identical sub-circuits within a single design. For example, FIG. 1 shows the eight (8) possible orientations for an “F” shaped element 10 of an IC design 12. Some implementations of hierarchical technology migration cannot handle situations where a sub-circuit exists in multiple orientations simultaneously. For example, most implementations cannot handle situations where a sub-circuit exists in rotated and non-rotated forms. The restrictions arise because it may be necessary to move a single shape in different directions due to the orientations of the owning sub-circuit. The algorithms required to handle these cases can either require “sum constraints” or they cause X and Y variables to become entangled, preventing one-dimensional optimization of the problem. FIG. 2 shows a sub-circuit 14 including an F-shaped element 10 and another circuit shape 16 (also labeled S) that will be used to describe the potential problems. Each shape 16 includes a left edge Xsl, a right edge Xsr, a top edge Yst and a bottom edge Ysb.
With regard to sum constraints, FIG. 3 shows two sub-circuits 14A, 14B that are placed such that they are adjacent one another. That is, one sub-circuit 14A, and another 14B, mirrored about the Y-axis 18. Sub-circuits 14A, 14B are located at an origin Xo. In this example, a circuit shape 16B of sub-circuit 14B that is close to the boundary of sub-circuit 14B has a spacing constraint applied to it. The spacing constraint may be, for example, a minimum separation distance (G) required between shapes 16A and 16B, within two sub-circuits 14A, 14B. Edge Xsl (the leftmost edge of a circuit shape 16 as shown in FIG. 2) is located at Xo+Xsl for sub-circuit 14A and Xo−Xsl for sub-circuit 14B. These two edges must be separated by more than minimum separation distance G. Accordingly, the following equations must be met:Xo+Xsl−(Xo−Xsl)>GXo+Xsl−Xo+Xsl>GXsl+Xsl>G.
These equations represent a “sum constraint” that cannot be solved by some solution techniques used in technology migration because they can only handle equations which are the difference of two variables.
FIG. 4 illustrates a 9° rotation of a sub-circuit 14C relative to a sub-circuit 14D, which has caused a swapping of the X and Y directions of movement for sub-circuit 14C. In particular, there are two origin placements for the sub-circuits 14D, 14C: one at X1, Y1 and another at X2, Y2, respectively. As a result of the rotation, minimal separation distance G is now applicable between a left edge Xsl of circuit shape 16D and a top edge Yst of circuit shape 16C. Accordingly, the following equations must be met:X2−Yst−(X1−Xsl)>=GX2−Yst−X1+Xsl>=G.
Since this constraint contains both X and Y values, it cannot be solved by one-dimensional technology migration methods.
In order to address the above-identified problems, clones of sub-circuits are created. The clones of a sub-circuit 14 are copies of the sub-circuit in all of the used orientations of the sub-circuit, e.g., as shown for F-shaped element 10 in FIG. 1. The clones are substituted in the hierarchy for the mirrored and rotated copies of sub-circuit 14, and this modified hierarchy is migrated. In this case, the original sub-circuit 14 may have been copied into as many as seven (7) additional sub-circuits, each representing a unique orientation. Unfortunately, cloning results in an increase in data volume. That is, the cloning into as many as seven (7) additional sub-circuits results in the worst case in a 7× increase in data volume. In addition, any manual design change that needs to be made to a sub-circuit must be made to all of its clones, which makes it more difficult for designers to deal with the post-migrated data. Furthermore, certain checking programs might not be able to handle these clones.
In order to minimize the impact of the cloning, it is desirable to combine the clones back into the original circuit shape, where possible, to form a single circuit shape. However, generating a single circuit shape that encompasses the original and clones is difficult due to slight differences that are created between the original and clone. FIG. 5 shows an illustrative rectangular 20A and upside-down L 22A original circuit shapes, and FIG. 6 shows overlapping clones 20B, 20C of rectangular circuit shape 20A, and overlapping clones 22B, 22C of upside-down L circuit shape 22A. The slight differences are caused by the differences in each clones” respective environment (e.g., the shapes surrounding each copy) and round-off errors caused by conversions between floating point and integer representations of shape, edge and circuit locations. In particular, when data is scaled, the coordinates of edges, which are integers, are multiplied by a scaling factor that is a floating point. The resulting floating point number must be converted back to an integer. Within a hierarchy, the location at each level of the hierarchy is subjected to this conversion, as is the final shape position within the cell, i.e., lowest hierarchy level. At each of these levels, there is a rounding taking place. These roundings may push edges one grid point in opposite directions, i.e., one may round up and one may round down, resulting in a mis-registration of two grid points. In addition, each of the clones has differing neighboring shapes, which may result in the clone's shapes needing to move differently when compared with the other clones. As a result, the original cannot be substituted for the clones without creating ground rule errors.
When all of the slightly different clones and original circuit are combined in a straightforward manner, the minor differences cause notches in the merged circuit shapes that are illegal. FIG. 7 illustrates a combining of rectangular circuit shapes 20A, 20B, 20C into rectangular shape 26 and upside-down L circuit shapes 22A, 22B, 22C into upside-down L shape 28 according to a straightforward one-dimensional method. Note the introduction of notches 24 into the shapes. These notches are the result of mis-registration, instances where the shapes were moved a small distance from their original location. These notches are undesirable and most likely are illegal.
In view of the foregoing, there is a need in the art for an improved method, system and program product for merging cloned and original circuit shapes.